<?php
/**
 * User: helloJiu
 * Date: 2021/11/2
 * Time: 9:52
 */

namespace App\Algorithm\DP;


class CanPartition
{
    /**
     * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * https://leetcode-cn.com/problems/partition-equal-subset-sum/
     * 使用动态规划解决
     * @param Integer[] $nums
     * @return Boolean
     */
    function canPartition($nums)
    {
        $sum = array_sum($nums);
        if ($sum % 2 != 0) {
            return false;
        }

        $half = $sum / 2;
        // $dp[$w]表示 当背包重量是$w时, 背包内的最大价值
        $dp = [];
        $n = count($nums);
        // 初始化背包
        for ($w = 0; $w <= $half; $w++) {
            $dp[$w] = 0;
        }

        for ($i = 1; $i <= $n; $i++) {
            for ($w = $half; $w > 0; $w--) {
                $remain_w = $w - $nums[$i - 1];
                if ($remain_w >= 0) {
                    // 还要剩余重量
                    $dp[$w] = max($dp[$remain_w] + $nums[$i - 1], $dp[$w]);
                }
            }
        }

        // 此时背包里包含各重量对应的最大价值, 判断最大价值是否等于$half
        return $dp[$half] == $half;

    }
}